一、DGCNN [2018]

《An End-to-End Deep Learning Architecture for Graph Classification》

1. 摘要：直接读取 graph 并对 graph 进行分类，有两个挑战：

   • 如何编码graph 中丰富的信息从而用于分类。为此论文 《An End-to-End Deep Learning Architecture for Graph Classification》 设计了一个局部图卷积模型（localized graph convolution model），并展示了它与两个 graph kernel 的联系。

   • 如何以一个有意义（meaningful）且一致的 （consistent）顺序来读取一个graph 。为此论文 《An End-to-End Deep Learning Architecture for Graph Classification》 设计了一个新颖的 SortPooling 层，该层以一致的顺序对图的节点进行排序，以便可以在图上训练传统的神经网络。

   在 benchmark 图分类数据集上的实验表明，所提出的架构与最先进的 graph kernel 和其他图神经网络方法相比，取得了极具竞争力的性能。此外，该架构允许使用原始图进行端到端的梯度训练，而不需要首先将图转化为向量。整个架构称之为 Deep Graph Convolutional Neural Network: DGCNN 。

2. 引言：过去几年中，神经网络在图像分类、自然语言处理、强化学习、以及时间序列分析等应用领域日益盛行。层与层之间的连接结构使神经网络适合处理张量形式的信号，其中张量元素以有意义的顺序排列。这种固定的输入顺序是神经网络提取高层次特征的基石。例如，如果我们随机混洗下图所示图像的像素，那么SOTA 的卷积神经网络就无法将其识别为一只鹰。

   

   虽然图像和许多其他类型的数据都是有自然的顺序，但还有另一大类结构化数据，即graph ，它们通常缺乏具有固定顺序的张量表示（tensor representation）。graph 的例子包括分子结构、知识图谱、生物网络、社会网络、以及有依赖关系的文本文档。有序张量表示的缺乏，限制了神经网络在图上的适用性。

   最近，人们对将神经网络推广到图上的兴趣越来越大：

   • 《Spectral networks and locally connected networks on graphs》 将卷积网络推广到谱域中的 graph，其中滤波器应用于图的频率模式（frequency mode）。这个频率模式由图傅里叶变换计算得到。

   • 图傅里叶变换涉及到与图拉普拉斯矩阵的特征向量的昂贵乘法。为了减少计算负担，《Convolutional neural networks on graphs with fast localized spectral filtering》将谱域滤波器参数化为特征值的 Chebyshev多项式，并实现了高效的和局部化的滤波器。

   上述谱域公式的一个局限性是：它们依赖于图拉普拉斯矩阵的固定频谱，因此只适合于具有固定单一结构的图。相反，空域公式不限于固定的图结构。为了提取局部特征，有几项工作独立提出在相邻节点之间传播特征。

   • 《Convolutional networks on graphs for learning molecular fingerprints》 提出了可微分的神经图指纹Neural Graph Fingerprint ，它在1-hop 邻居之间传播特征，以模拟传统的圆形指纹（circular fingerprint）。

   • 《Diffusion-convolutional neural networks》 提出了 Diffusion-CNN，它使用不同的权重将不同hop 的邻居传播到中心节点。

   • 后来，《Semi-supervised classification with graph convolutional networks》 开发了针对 《Convolutional neural networks on graphs with fast localized spectral filtering》 提出的谱域卷积的一阶近似，这也导致了相邻节点之间的传播。

   • 《Learning convolutional neural networks for graphs》 提出了另一种空域图卷积的方式，从节点的邻域中提取固定大小的 local patch ，并用 graph labeling 方法和 graph canonization 工具对这些 patch 进行线性化处理。由此产生的算法被称为 PATCHY-SAN 。

   由于空域方法不需要单一的图结构，它们可以被应用于节点分类和图分类任务。虽然取得了 SOTA 的节点分类结果，但以前的大多数工作在图分类任务上的表现相对较差。其中一个原因是，在提取局部节点特征后，这些特征被直接 sum 从而用于图分类的图的 graph-level 特征。在论文 《An End-to-End Deep Learning Architecture for Graph Classification》 中，作者提出了一个新的架构，可以保留更多的节点信息并从全局图的拓扑结构中进行学习。一个关键的创新是一个新的 SortPooling 层，它从空域图卷积中获取图的无序节点特征作为输入。SortPooling 不是将这些节点特征相加，而是将它们按照一致的顺序排列，并输出一个固定大小的 sorted graph representation ，这样传统的卷积神经网络就可以按照一致的顺序读取节点并在这个 representation上进行训练。作为图卷积层和传统神经网络层之间的桥梁，SortPooling 层可以通过它来反向传播损失的梯度，将 graph representation 和 graph learning 融合为一个端到端的架构。

   论文贡献如下：

   • 论文提出了一个新颖的端到端深度学习架构，用于图分类。它直接接受图作为输入，不需要任何预处理。

   • 论文提出了一个新颖的空域图卷积层来提取多尺度（multi-scale）的节点特征，并与流行的 graph kernel 进行类比，从而解释为什么它能发挥作用。

   • 论文开发了一个新颖的 SortPooling 层来对节点特征进行排序，而不是将它们相加，这样可以保留更多的信息，并允许我们从全局范围内学习。

3. 相关工作：

   • Graph Kernel：Graph Kernel 通过计算一些半正定的 graph similarity 度量，使 SVM 等 kernel machine 在图分类中变得可行，在许多图数据集上取得了 SOTA 的分类结果。

     • 一个开创性的工作是在 《Convolution kernels on discrete structures》中引入了 convolution kernel ，它将图分解成小的子结构（substructure），并通过增加这些子结构之间的成对相似度来计算核函数 （kernel function）。常见的子结构类型包括 walk、subgraph 、path 、以及 subtree 。

     • 《Graph invariant kernels》 以一种通用的方式重新表述了许多著名的基于子结构的核，称为图不变核（ graph invariant kernel）。

     • 《Deep graph kernels》 提出了 deep graph kernel ，它学习子结构的潜在representation 从而利用其依赖信息。

     convolution kernel 根据两个图的所有子结构对进行比较。另一方面，assignment kernel 倾向于找到两个图的子结构之间的对应关系。

     • 《An aligned subtree kernel for weighted graphs》 提出了包含显式子树对应关系的 aligned subtree kernel 。

     • 《On valid optimal assignment kernels and applications to graph classification》 为一种类型的 hierarchy-induced kernel 提出了最佳分配。

     大多数现有的 graph kernel 侧重于对比小的局部模式。最近的研究表明，对比图的全局模式可以提高性能。《Discriminative embeddings of latent variable models for structured data》 使用 latent variable model 表示每个图，然后以类似于 graphical model inference 的方式显式地将它们嵌入到特征空间。结果在准确性和效率方面与标准 graph kernel 相比都很好。

     DGCNN 与一类基于 structure propagation 的 graph kernel 密切相关，具体而言是 Weisfeiler-Lehman(WL) subtree kernel 和 propagation kernel (PK) 。为了编码图的结构信息，WL 和 PK 基于中心节点的邻居的特征迭代更新中心节点的特征。WL 对 hard 节点标签进行操作，而 PK 对 soft 标签分布进行操作。由于这种操作可以有效地实现为随机行走，这些 graph kernel 在大型图上是有效的。与WL和PK相比，DGCNN有额外的参数 $\mathbf{W}$$\mathbf W$，这些参数是通过端到端优化训练的。这允许从标签信息中进行有监督的特征学习，使得它不同于 graph kernel 的两阶段框架。

   • 用于图的神经网络：

     • 将神经网络推广到图的研究有两条线：给定一个单一的图结构，推断单个节点的标签或者单个图的标签；给定一组具有不同结构和大小的图，预测未见过的图的类标签（图分类问题）。

       在本文中，我们专注于第二个问题，这个问题更加困难，因为：图的结构不是固定的，每个图内的节点数量也不是固定的。此外，在第一个问题中来自不同图的节点具有固定的索引或对应的索引，但是在第二个问题中节点排序往往是不可用的。

     • 我们的工作与一项使用CNN 进行图分类的开创性工作有关，称为 PATCHY-SAN。为了模仿 CNN 在图像上的行为，PATCHY-SAN 首先从节点的邻域中提取固定大小的局部 patch 作为卷积滤波器的感受野。然后，为了在这些 patch 上应用 CNN ，PATCHY-SAN 使用外部软件（如图规范化工具NAUTY）在预处理步骤中为整个图定义一个全局节点顺序，以及为每个 patch 定义一个局部顺序。之后，graph 被转换为有序的 tensor representation ，并在这些张量上训练 CNN 。

       虽然取得了与 graph kernel 有竞争力的结果，但这种方法的缺点包括繁重的数据预处理、以及对外部软件的依赖。我们的DGCNN 继承了其为图节点施加顺序的思想，但将这一步骤集成到网络结构中，即 SortPooling 层。

     • 在如何提取节点特征方面，DGCNN 也与 GNN、Diffusion-CNN 、以及 Neural Graph Fingerprint 相关。然而，为了进行graph-level 分类，GNN 监督单个节点（是一个虚拟的超级节点，它节点与所有其它真实节点相连），而 Diffusion-CNN 和 Neural Graph Fingerprint 使用 sum 的节点特征。相比之下，DGCNN 以某种顺序对节点进行排序，并将传统的CNN 应用于有序的 representation 上，这样可以保留更多的信息，并能从全局图拓扑结构中学习。

1.1 模型

1. 给定图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ ，其中 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n\}$ 为节点集合，$\mathcal{E}=\{e_{i,j}\}$$\mathcal E=\{e_{i,j}\}$ 为边集合。

   • $\mathbf{A}\in {\mathbb{R}}^{n\times n}$$\mathbf A\in \mathbb R^{n\times n}$ 为邻接矩阵。这里我们仅考虑最简单的无向图，即 $\mathbf{A}$$\mathbf A$ 是对称的 0/1 矩阵。并且图中没有自环（self-loop）。

   • 每个节点 $v_i$$v_i$ 包含一个输入特征向量 ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^{d_f}$$\mathbf{\vec x}_i\in \mathbb R^{d_f}$ 。所有节点的输入特征向量构成输入特征矩阵 $\mathbf{X}\in {\mathbb{R}}^{n\times d_f}$$\mathbf X\in \mathbb R^{n\times d_f}$ 。

   • ${\mathcal{N}}_i$$\mathcal N_i$ 表示节点 $v_i$$v_i$ 的邻居节点集合。

2. DGCNN 包含三个连续的阶段：

   • 图卷积层（ graph convolution layer ）抽取节点的局部子结构特征，并定义一致的节点顺序。

   • SortPooling 层按照前面定义的顺序对节点特征进行排序，并统一输入尺寸 size 。

   • 传统的卷积层和dense 层读取排序的graph representation 并进行预测。

   DGCNN 整体架构如下图所示：图数据首先通过多个图卷积层，其中节点信息在邻域之间传播；然后对节点特征排序并通过 SortPooling 层池化；然后传递给传统的 CNN 结构以学习模型。节点特征以颜色来可视化。

   

1.1.1 图卷积层

1. 我们的图卷积层的形式为：

   $$\mathbf{Z}=f\left({\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{A}}\mathbf{X}\mathbf{W}\right)$$

   其中：

   • $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$\tilde{\mathbf A}=\mathbf A + \mathbf I$ 为带self-loop 的邻接矩阵。$\tilde{\mathbf{D}}$$\tilde{\mathbf D}$ 为对应的度矩阵，${\tilde{D}}_{i,i}=\sum _j{\tilde{A}}_{i,j}$$\tilde D_{i,i} = \sum_j \tilde A_{i,j}$ 。

   • $\mathbf{W}\in {\mathbb{R}}^{d_f\times d}$$\mathbf W\in \mathbb R^{d_f\times d}$ 为可训练的权重矩阵，$d$$d$ 为输出的特征维度。

   • $f(\cdot )$$f(\cdot)$ 为非线性激活函数。

2. 图卷积层聚合局部邻域的节点信息从而抽取局部子结构。为了抽取多尺度（multi-scale）的子结构特征，我们堆叠多个图卷积层。第 $l$$l$ 层卷积层为：

   $${\mathbf{Z}}^{(l+1)}=f\left({\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{A}}{\mathbf{Z}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

   其中：

   • ${\mathbf{Z}}^{(0)}=\mathbf{X}$$\mathbf Z^{(0)} = \mathbf X$ 为初始的 representation ，${\mathbf{Z}}^{(l)}\in {\mathbb{R}}^{n\times d_l}$$\mathbf Z^{(l)}\in \mathbb R^{n\times d_l}$ 为第 $l$$l$ 层的 representation 。$d_l$$d_l$ 为第 $l$$l$ 层的特征维度。

   • ${\mathbf{W}}^{(l)}\in {\mathbb{R}}^{d_l\times d_{l+1}}$$\mathbf W^{(l)}\in \mathbb R^{d_l\times d_{l+1}}$ 为第 $l$$l$ 层的、可训练的权重矩阵。

   假设一共有 $L$$L$ 层，则我们将这 $L$$L$ 个输出进行水平拼接，记作：

   $${\mathbf{Z}}^{(1:L)}=[{\mathbf{Z}}^{(1)},\cdots ,[{\mathbf{Z}}^{(L)}]\in {\mathbb{R}}^{n\times \sum _{l=1}^L{d}_l}$$

   拼接的结果 ${\mathbf{Z}}^{(1:L)}$$\mathbf Z^{(1:L)}$ 每一行被称作节点的一个特征描述符（feature descriptor），它编码了节点的多尺度局部子结构信息（multi-scale local substructure information） 。

3. 我们的图卷积层和 GCN 层很相似，区别在于它们使用不同的传播矩阵。

   GCN layer 采用 ${\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}$$\tilde{\mathbf D}^{-1/2}\tilde{\mathbf A} \tilde{\mathbf D}^{-1/2}$ 作为传播矩阵，它本质上就等价于 ${\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{A}}$$\tilde{\mathbf D}^{-1}\tilde{\mathbf A}$ 。论文的表述有误。

4. 可以证明，我们的图卷积层有效地模仿了两个流行的 graph kernel （Weisfeiler-Lehman subtree kernel、propagation kernel）的行为，这有助于解释其graph-level 分类行为。

   • WL-test 对节点邻域进行反复迭代，最终根据两个图之间的节点label 是否完全相同，从而判断两个图是否同构的。注：这里的 label 更多地是节点的离散特征，而不是节点的监督信息。

     WL-test 迭代过程如下：聚合节点及其邻域的 label ；将聚合后的label 经过哈希函数得到不同的、新的label ，即 relabel 。

     《Weisfeiler-lehman graph kernels》 根据 WL-test 提出了 WL subtree kernel 来衡量两个图的相似性。核函数利用 WL tet 的不同迭代中使用的节点label 数作为图的特征向量。直观地讲，WL test 第 $k$$k$ 次迭代中节点 label 代表了以该节点为根的、高度为 $k$$k$ 的子树结构。因此 WL subtree kernel 考虑的图特征本质上是不同根子树的计数。

     如果我们记 $\tilde{\mathbf{X}}=\mathbf{X}\mathbf{W}$$\tilde{\mathbf X} = \mathbf X\mathbf W$ ，则我们的图卷积层改写为：

     $${\overrightarrow{\mathbf{z}}}_i=f\left(\frac{1}{{\tilde{D}}_{i,i}}({\widetilde{\overrightarrow{\mathbf{x}}}}_i+\sum _{j\in {\mathcal{N}}_i}{\widetilde{\overrightarrow{\mathbf{x}}}}_j)\right)$$

     我们可以视 ${\widetilde{\overrightarrow{\mathbf{x}}}}_i$$\tilde{\mathbf{\vec x}}_i$ 为节点 $v_i$$v_i$ 的连续颜色（continuous color）。因此我们的图卷积公式可以视为 WL-test 算法的一个 soft 版本。

     soft 版本有两个好处：

     • 首先，卷积参数 $\mathbf{W}$$\mathbf W$ 允许对节点的原始特征矩阵 $\mathbf{X}$$\mathbf X$ 进行分层特征抽取，并可以通过反向传播进行训练。这比 WL subtree kernel 具有更好的表达能力。

     • 其次，使用稀疏矩阵乘法更容易实现 soft WL-test，避免了读取和排序可能非常长的 WL signature 字符串。

   • propagation kernel:PK 比较了两个图的label 分布，它基于扩散更新的方案（diffusion update scheme）：

     $${\mathbf{L}}^{(l+1)}=\mathbf{T}{\mathbf{L}}^{(l)}$$

     其中：

     • $\mathbf{T}={\mathbf{D}}^{-1}\mathbf{A}$$\mathbf T= \mathbf D^{-1} \mathbf A$ 为图上的随机游走转移概率矩阵。

     • ${\mathbf{L}}^{(l)}\in {\mathbb{R}}^{n\times c}$$\mathbf L^{(l)}\in \mathbb R^{n\times c}$ 表示 $n$$n$ 个节点在第 $l$$l$ 轮迭代的、$c$$c$ 维的label distribution 向量。其初始值就是每个节点label 的 one-hot 。

     最终将所有迭代过程中的label distribution 向量通过 locality-sensitive hashing:LSH 映射到离散的分桶，从而计算 label distribution 向量之间的相似性。

     PK 具有和 WL kernel 类似的 graph 分类性能，甚至具有更高的效率。而我们的图卷积公式和PK 非常相似。

   WL kernel 在 hard vertex label 上进行，而 PK 在 soft label distribution 上进行。这些操作都可以有效地实现为随机游走，因此这些核函数在大规模图上非常有效。和 WL kernel 和 PK 相比，DGCNN 在传播之间具有其它参数，这些参数是通过端到端优化进行训练的。这允许从标签信息中进行有监督的特征学习，使其不同于 graph kernel 的两阶段框架。

5. WL kernel 的基本思想是将节点的颜色和其1-hop 邻域的颜色拼接起来作为节点的 WL-signature，然后按照字典顺序对 signature 字符串进行排序从而分配新的颜色。具有相同signature 的节点将分配相同的新颜色。

   这种 “聚合--分配” 动作和我们的图卷积层是类似的，因此我们称 ${\mathbf{Z}}^{(l)}$$\mathbf Z^{(l)}$ 为连续的 WL color 。

1.1.2 SortPooling 层

1. SortPooling 层的主要功能是将特征描述符输入传统的 1-D 卷积层和 dense 层之前，以一致的顺序对特征描述符进行排序，其中每个特征描述符对应于一个节点。

   问题是：以什么样的顺序对节点进行排序？在图像分类中，像素天然地以某种空间顺序排序。在NLP 任务中，可以使用字典顺序对单词进行排序。在图中，我们可以根据节点在图中的结构角色（structural role）对节点进行排序。

   一些工作使用 graph labeling 方法（如 WL kernel）来在预处理阶段对节点进行排序，因为最终的 WL color 定义了基于图拓扑的排序。WL 施加的这种节点顺序在各个图之间是一致的，这意味着如果两个不同图中的节点在各自图中具有相似的结构角色，那么它们会被分配以相似的相对位置。结果，神经网络可以按顺序读取图节点并学习有意义的模型。

   在DGCNN 中，我们也使用 WL color 来对节点进行排序。幸运的是，我们已经看到图卷积层的输出正好是连续的 WL color ${\left\{{\mathbf{Z}}^{(l)}\right\}}_{l=1,\cdots ,L}$$\left\{\mathbf Z^{(l)}\right\}_{l=1,\cdots,L}$ ，可以利用它们进行排序。遵循这个思路，我们提出了一种新的 SortPooling 层。对于 SortPooling 层：

   • 输入是一个 $n\times \sum _{l=1}^L{d}_l$$n\times \sum_{l=1}^L d_l$ 的张量 ${\mathbf{Z}}^{(1:L)}$$\mathbf Z^{(1:L)}$ ，其中每一行代表一个节点的特征描述符，每一列代表一个特征通道（feature channel）。

   • 输出是一个 $k\times \sum _{l=1}^L{d}_l$$k\times \sum_{l=1}^Ld_l$ 的张量，其中 $k$$k$ 为用于预定义的一个整数。

   在 SortPooling 层中，首先根据 ${\mathbf{Z}}^{(L)}$$\mathbf Z^{(L)}$ 按行对 ${\mathbf{Z}}^{(1:L)}$$\mathbf Z^{(1:L)}$ 进行排序。我们可以认为最后一层的输出是节点的最细粒度的WL color ，并根据这个 final color 对所有节点进行排序。

   通过这种方式，我们对图节点施加了一致的排序，从而可以在排序的graph representation 上训练传统的神经网络。理想情况下，我们需要图卷积层足够深（意味着 $L$$L$ 足够大），以便 ${\mathbf{Z}}^{(L)}$$\mathbf Z^{(L)}$ 能够将节点尽可能地细粒度地划分为不同颜色。

2. 基于 ${\mathbf{Z}}^{(L)}$$\mathbf Z^{(L)}$ 的节点排序是通过使用 ${\mathbf{Z}}^{(L)}$$\mathbf Z^{(L)}$ 的最后一个通道以降序来对节点进行排序的（即 node representation 的最后一维）。

   • 如果两个节点在 ${\mathbf{Z}}^{(L)}$$\mathbf Z^{(L)}$ 的最后一个通道中具有相同的值，那么比较倒数第二个通道的值，依此类推。

   • 如果两个节点在 ${\mathbf{Z}}^{(L)}$$\mathbf Z^{(L)}$ 的所有通道取值相等，则比较 ${\mathbf{Z}}^{(L-1)},{\mathbf{Z}}^{(L-2)},\cdots$$\mathbf Z^{(L-1)},\mathbf Z^{(L-2)},\cdots$ 等通道上的取值，依此类推。

3. 除了一致性的顺序对节点特征进行排序外，SortPooling 还有一个能力是统一输出张量的尺寸（size）。

   排序后，我们将输出张量的尺寸从 $n$$n$ 截断/扩张为 $k$$k$ 。目的是统一graph size，使得不同数量节点的图将其大小同一为 $k$$k$ ：

   • 如果 $n>k$$n\gt k$ ，则删除最后的 $n-k$$n-k$ 行。

   • 如果 $n<k$$n\lt k$ ，则在最后添加 $k-n$$k-n$ 行全零。

   这和 LGCN的 k-largest 节点选择方法很类似。只是LGCN 独立地选择并排序最大的 k 个特征，而 SortPooling 根据 final color 选择最大的 k 个节点。除此之外，LGCN 和 DGCNN 还有一个最大的区别：

   • LGCN 中，卷积层用于根据邻域节点的 k-largest representation 来更新中心节点的 representation，因此最终用于节点分类。

   • DGCNN 中，卷积层根据所有节点的 GCN representation 来获得 graph representation，因此最终用于图分类。

4. 作为图卷积层和传统层之间的桥梁，SortPooling 还有另一个好处，就是通过它可以记住输入的排序顺序从而将损失梯度传递给前一层，从而可以训练前一层的参数。

   相比之下，一些工作在预处理阶段对节点进行排序，因此无法在排序之前进行参数训练。

1.1.3 其它层

1. 在 SortPooling 层之后，我们得到一个大小为 $k\times \sum _{l=1}^L{d}_l$$k\times \sum_{l=1}^Ld_l$ 的张量 ${\mathbf{Z}}^{(\text{sp})}$$\mathbf Z^{(\text{sp})}$ ，其中每一行代表一个节点、每一列代表一个特征通道。

   • 为了在 ${\mathbf{Z}}^{(\text{sp})}$$\mathbf Z^{(\text{sp})}$ 之上训练 CNN，我们添加若干个 1-D 卷积层和最大池化层，从而学习节点序列上的局部模式。

   • 最后我们添加一个全连接层和一个 softmax 输出层。

1.1.4 讨论

1. GNN 设计的一个重要标准是：网络应该将同构图（isomorphic graph）映射到相同的representation ，并且输出相同的预测。否则邻接矩阵中的任何排列（permutation）都可能对同一个图产生不同的预测。

   对于基于求和的方法这不是问题，因为求和对于节点排列是不变的。但是对于排序的方法DGCNN, PATCHY-SAN 需要额外注意。

   为了确保将同构图预处理为相同的张量，PATCHY-SAN 首先使用 WL kernel 算法，然后使用图规范化工具 NAUTY 。尽管 NAUTY 对于小图足够有效，但是理论上讲，图规范化（graph canonization）问题至少在计算上和图同构检验一样困难。

   相比之下，我们表明DGCNN 可以避免这种图规范化步骤。DGCNN 使用最后一个图卷积层的输出对节点进行排序，我们表明：这可以视为是 soft WL 输出的连续颜色。因此 DCNN 能够将节点排序视为图卷积的副产品，从而避免像 PATCHY-SAN 这样显式运行运行 WL kernel 算法。并且，由于 SortPooling 中的排序方案，DGCNN 不再需要图规范化。因此 DGCNN 不需要显式运行 WL kernel 或 NAUTY，这使我们摆脱了数据预处理和外部软件的束缚。

   我们还指出，尽管 DGCNN 在训练过程中会动态地对节点进行排序，但是随着时间的增加，节点顺序会逐渐变得稳定。这是因为参数 $\mathbf{W}$$\mathbf W$ 在所有节点之间共享。$\mathbf{W}$$\mathbf W$ 的更新将同时增加或减少所有节点的 continuous WL color 。此外，训练过程中 $\mathbf{W}$$\mathbf W$ 的学习率会逐渐降低，从而使得整个节点的排序在整个过程中保持稳定。

2. 定理：在 DGCNN 中，如果两个图 ${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1, \mathcal G_2$ 是同构的，则在 SortPooling 之后它们的图representation 是相同的。

   证明：注意，第一阶段的图卷积对于节点索引是不变的。因此，如果 ${\mathcal{G}}_1$$\mathcal G_1$ 和 ${\mathcal{G}}_2$$\mathcal G_2$ 是同构的，那么在图卷积之后它们将具有相同的特征描述符的 multiset 。

   由于 SortPooling 对于节点排序的方式是：当且仅当两个节点具有完全相同的特征描述符时，两个节点才有联系have a tie，因此排序的representation 对于两个节点的排名具有不变性。因此，在 SortPooling 之后，${\mathcal{G}}_1,{\mathcal{G}}_2$$\mathcal G_1,\mathcal G_2$ 具有相同的representation 。

1.2 实验

1.2.1 Graph Kernel 比较

1. 数据集：五个benchmark 生物信息学数据集，包括MUTAG、PTC、 NCI1、 PROTEINS、D&D 。所有节点都有 label 信息。

2. baseline 方法：四种graph kernel，包括 graphlet kernel: GK、random walk kernel: RW、propagation kernel: PK、Weisfeiler-Lehman subtree kernel: WL 。

3. 实验配置：使用 LIBSVM 进行10-fold 交叉验证，训练集为 9 fold、测试集为 1 fold，并使用训练集中的 1 fold 进行超参数搜索。

   每个实验重复 10次（因此每个数据集训练了 100 次），报告了平均的准确率和标准差。

4. 实验结果如下表所示，可以看到：

   • DGCNN 相比 graph kernel 具有很强的竞争力。

   • 另外 DGCNN 通过 SGD 进行训练，避免了 graph kernel 所需的 $O(n^2)$$O(n^2)$ 的计算复杂度。因此，当应用于工业规模的图数据集时，我们预期 DGCNN 优势更大。

   

1.2.2 GNN 比较

1. 数据集：六个数据集，其中包括三个生物信息学数据集 NCI1, PROTEINS, D&D 、三个社交网络数据集 COLLAB, IMDB-B, IMDB-M 。这些社交网络数据集中的图没有节点label，因此是纯结构。

2. baseline ：四种深度学习方法，包括PATCHY-SAN: PSCN, DiffusionCNN: DCNN, ECC, Deep Graphlet Kernel: DGK 。

3. 实验配置：对于 PSCN, ECC, DGK，我们报告原始论文中的最佳结果，因为他们实验配置和我们这里相同。对于 DCNN，我们使用我们的实验配置重新实验。

   PSCN, ECC 能够额外地利用边特征，但是由于这里很多数据集没有边特征，以及其它一些方法无法使用边特征，因此这里都没有利用边特征来评估效果。

4. 实验结果如下表所示，可以看到：

   • DGCNN 在PROTEINS, D&D, COLLAB, IMDB-M 数据集上表现出最高的分类准确率。

   • 和 PATCHY-SAN 相比，DGCNN 的改进可以解释如下：

     • 通过使梯度信息通过 SortPooling 向后传播，DGCNN 甚至可以在排序开始之前就启用参数训练，从而实现更好的表达能力。

     • 通过动态排序节点，DGCNN 不太可能过拟合特定的节点排序。相比之下，PATCHY-SAN 遵从预定义的节点顺序。

   • DGCNN 的另一个巨大优势是：它提供了一种统一方法，将预处理集成到神经网络结构中。

   • 和使用 sum 节点特征来分类的 DCNN 相比，DGCNN 表现出显著的提升。

   • 为了证明SortPooling 优于求和的优势，我们进一步列出了 DGCNN(sum) 的结果，该结果采用 sum layer 替换 DGCNN 的 SortPooling 和后面的 1-D 卷积层。可以看到，大多数情况下性能下降很多。